# 基数排序
from utils.array_utils import check_all
import math


def sort_01(l):
    """ 将整型列表 排序
    只支持自然数"""
    for t in range(len(str(min(l))), len(str(max(l))) + 1):
        # print(t, '--')
        # bucket = 10 * [[]] # 这样不行, 因为bucket里每个字列表都指向一个地址
        bucket = [[] for _ in range(10)] # 列表解析
        for i in l:
            # print(i % 10**t)
            index = i % 10 ** t // 10 ** (t - 1)
            bucket[index].append(i)
            # print(bucket[index])
        i = 0
        for item in bucket:
            for num in item:
                l[i] = num
                i += 1
                # l.append(num)
    return l


def sort_02(l):
    """ 将字符串列表排序
    ASCII码表(0~127): 空格:32 0:48 A:65 a:97 DEL:127
     ord('a') = 97, ord('z') = 122
     字符串排序--字典序
        1.等长: 逐个比较
        2.不等长: 短的从尾部补齐, 用最低的ASCII补, 之后再比
     """
    # 获取最长的字符串长度
    max_len = 0
    for i in l:
        if len(i) > max_len:
            max_len = len(i)

    for t in range(1, max_len + 1):
        # t: 代表从后到前获取字符串每一位的内容
        # print('\n', t, '---')
        bucket = [[] for _ in range(128)]
        for s in l:
            # s: 从l列表中的字符串
            # print(s[-1 * t], end='..')
            # 字符串长度不够长的话, 用最小的ascii号向后补齐
            temp = s
            for x in range(max_len - len(s)):
                temp += chr(0)
            index = ord(temp[-1 * t])
            # 入桶
            bucket[index].append(s)

        i = 0
        for item in bucket:
            # 出桶
            for con in item:
                l[i] = con
                i += 1
        # print(l)
    # print(l)
    return l


def sort_03(l):
    """ 将整型列表 排序
    支持所有整型"""
    min_num = min(l)
    max_num = max(l)
    # range_right 是列表所有数字中最长的位数(不包括负号), 考虑到负数因素, 要将最大值最小值求绝对值后再比较
    range_right = len(str(abs(max_num))) if abs(max_num) > abs(min_num) else len(str(abs(min_num)))
    for t in range(1, range_right + 1):
        # print(t, '--')
        # bucket = 10 * [[]] # 这样不行, 因为bucket里每个字列表都指向一个地址
        # 正数桶(包括0)
        bucket_big = [[] for _ in range(10)]
        # 负数桶
        bucket_small = [[] for _ in range(10)]
        for i in l:
            # 入桶
            # print(i % 10**t)
            index = abs(i) % 10 ** t // 10 ** (t - 1)
            if i >= 0:
                bucket_big[index].append(i)
            else:
                bucket_small[index].append(i)

        # print(bucket_small, '||', bucket_big)

        i = 0
        # 出桶
        for item in bucket_small[::-1] + bucket_big:
            for num in item:
                l[i] = num
                i += 1
    return l


if __name__ == '__main__':
    l = [9, -410, 265, 530, 530, -118600, 789, 110, -9, 0, 8, 1, 9]
    # l = [-129, -672, -709, 605, 710, 24, 232, 833, 644, 345]
    print(sort_03(l))
    # l = ['zhe', 'lin1', 'anna', 'nasa', 'papa', 'aaa', 'aa']
    # print('sorted: ', sort_02(l))
    # l = ['zhe', 'lin1', 'anna', 'nasa', 'papa', 'aaa', 'aa']
    # l.sort()
    # print(l)
    print(check_all(sort_02, 10, 'str'))
    print(check_all(sort_03, 10, 'int'))
